package org.kfive.nova.algorithm.sort;

import com.google.common.collect.Lists;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Created by Administrator on 2017/3/27.
 */
public class BucketSort {

    public void sort(List<Integer> data,Integer bucketSize){
        int len = data.size();
        Integer max = Collections.max(data);
        Integer min = Collections.min(data);
        int space = Double.valueOf(Math.floor((max-min+1)/bucketSize)).intValue();
        List<Integer>[] buckets = new ArrayList[bucketSize];

        for (int i=0;i<data.size();i++){
            int index = (data.get(i)-min)/space%bucketSize;
            if(buckets[index]==null){
                buckets[index] = new ArrayList<Integer>();
                buckets[index].add(data.get(i));
            }else {
                buckets[index].add(data.get(i));
                int k = buckets[index].size()-1;
                while (k>=1){
                    if(data.get(i)<buckets[index].get(k-1)){
                        buckets[index].set(k,buckets[index].get(k-1));
                    }
                    k--;
                }
                buckets[index].set(k,data.get(i));
            }
        }
        data.clear();
        for (int i=0;i<bucketSize;i++){
            for (int j=0;j<buckets[i].size();j++){
                data.add(buckets[i].get(j));
            }
        }


    }

    public static void main(String[] args) {
        BucketSort bucketSort = new BucketSort();
        List data = Lists.newArrayList(8,7,6,5,4,3,2,1,9);
        bucketSort.sort(data,3);
        System.out.println(data);

    }
}
